home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / bb_tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  1.7 KB  |  82 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  bb_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #ifndef LEDA_BB_TREE_H
  18. #define LEDA_BB_TREE_H
  19.  
  20. //------------------------------------------------------------------------------
  21. //
  22. // bb_tree:  
  23. //
  24. //           derived from class "bin_tree"
  25. //
  26. // Ijon Tichy (1993)
  27. //
  28. //------------------------------------------------------------------------------
  29.  
  30.  
  31. #include <LEDA/basic.h>
  32. #include <LEDA/impl/bin_tree.h>
  33.  
  34.  
  35. typedef bin_tree_node* bb_tree_item;
  36.  
  37.  
  38. // ----------------------------------------------------------------
  39. // class bb_tree
  40. // ----------------------------------------------------------------
  41.  
  42. // const float alpha = 0.28;
  43. // const float d     = 0.58;
  44.  
  45. // we multiply alpha, d, and all balances by 64 to make them integers
  46.  
  47.   const int alpha = 18; // 0.28 * 64
  48.   const int d = 37;     // 0.58 * 64
  49.  
  50. class bb_tree : public virtual bin_tree
  51. { 
  52.  
  53.   int root_balance() { return 2; }
  54.   int node_balance() { return 2; }
  55.   int leaf_balance() { return 1; }
  56.  
  57.   void rebal(bb_tree_item,int);
  58.   void insert_rebal(bb_tree_item);
  59.   void del_rebal(bb_tree_item, bb_tree_item);
  60.  
  61.  
  62.   float balance(bb_tree_item p)
  63.   { if (p->is_leaf()) 
  64.        return 0.5 ;
  65.     else 
  66.        return float(p->child[left]->get_bal())/p->get_bal();
  67.    }
  68.  
  69. public:
  70.  
  71.   bb_tree() {}
  72.  ~bb_tree() {}
  73.  
  74.   bb_tree(const bb_tree& T) : bin_tree(T) {}
  75.  
  76.   bb_tree& operator=(const bb_tree& T) 
  77.   { bin_tree::operator=(T); return *this; }
  78.  
  79. };
  80.  
  81. #endif
  82.